package com.zjsru.plan2023.oneday;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: CookLee
 * @Date: 2023/6/29
 *
 * 重构 2 行二进制矩阵
 * 第 0 行的元素之和为 upper。
 * 第 1 行的元素之和为 lower。
 * 第 i 列（从 0 开始编号）的元素之和为 colsum[i]，colsum 是一个长度为 n 的整数数组。
 *
 * 输入：upper = 2, lower = 1, colsum = [1,1,1]
 * 输出：[[1,1,0],[0,0,1]]
 * 解释：[[1,0,1],[0,1,0]] 和 [[0,1,1],[1,0,0]] 也是正确答案。
 *
 * 输入：upper = 2, lower = 3, colsum = [2,2,1,1]
 * 输出：[]
 *
 * 输入：upper = 5, lower = 5, colsum = [2,1,2,0,1,0,1,2,0,1]
 * 输出：[[1,1,1,0,1,0,0,1,0,0],[1,0,1,0,0,0,1,1,0,1]]
 */
public class ReconstructMatrix {
    
    public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
        //sum 为closum数组的和
        int sum = 0;
        int len = colsum.length;
        //two 为数组 colsum 中 2 的个数
        int two = 0;
        for (int i = 0; i < len; i++) {
            if (colsum[i] == 2) {
                two++;
            }
            sum += colsum[i];
        }
        //如果总数小于两个参数和或者 某一列是为2时 存在最小数小于为2的列数，否则代表数字越界
        if (sum != upper + lower || Math.min(upper, lower) < two) {
            return new ArrayList<>();
        }
        //two代表为2的个数，特殊处理，减去后的数字代表总值为1或者小于1的数字
        upper -= two;
      
        //构建返回的数据结构
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < 2; ++i) {
            res.add(new ArrayList<>());
        }
        for (int i = 0; i < len; i++) {
            if (colsum[i] == 2) {
                //代表为2的列，只要保证数字两列数字相加为2即可
                res.get(0).add(1);
                res.get(1).add(1);
            } else if (colsum[i] == 1) {
                if (upper > 0) {
                    //代表为1的列，但是还有其他数字剩余，保证数字两列数字相加为1即可,upper是否有值即填充第一行的数字
                    res.get(0).add(1);
                    res.get(1).add(0);
                    --upper;
                } else {
                    //代表为1的列，但是没有还有其他数字剩余，即为1就行，与上文对调
                    res.get(0).add(0);
                    res.get(1).add(1);
                }
            } else {
                //没有数字要求，相加即为0就行
                res.get(0).add(0);
                res.get(1).add(0);
            }
        }
        return res;
    }
    
    public static void main(String[] args) {
        ReconstructMatrix reconstructMatrix = new ReconstructMatrix();
        int upper = 2, lower = 1;
        int[] colsum = new int[] {1, 1, 1};
        System.out.println(reconstructMatrix.reconstructMatrix(upper, lower, colsum));
    }
    
    
}
